/*
 * @lc app=leetcode.cn id=37 lang=javascript
 *
 * [37] 解数独
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  // y轴已填入的数字
  let ys = Array.from({length: 9}, () => [])
  // X轴已入的数字 
  let xs = Array.from({length: 9}, () => [])
  // 9宫格已填入的数字
  let cells = Array.from({length: 3}, () => Array.from({length: 3}, () => []))
  // 初始化已填入的数字
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (board[y][x] !== '.') {
        let index = board[y][x] - 1
        ys[y][index] = true 
        xs[x][index] = true
        cells[Math.floor(y / 3)][Math.floor(x / 3)][index] = true
      }
    }
  }

  const dfs = (y, x) => {
    // 到最左侧就到下一行第一个
    if (x === 9) {
      x = 0
      y ++
      // 到最后一个了,成功
      if (y === 9) {
        return true
      }
    }
    // 没有填入数字,填入
    if (board[y][x] === '.') {
      for (let i = 0; i < 9; i++) {
        let canUse = !ys[y][i] && !xs[x][i] && !cells[Math.floor(y/3)][Math.floor(x/3)][i]
        // 可填入
        if (canUse) {
          board[y][x] = `${i + 1}`
          ys[y][i] = true
          xs[x][i] = true
          cells[Math.floor(y / 3)][Math.floor(x / 3)][i] = true
          // 如果填入合法
          if (dfs(y, x +1)) {
            return true
          }
          // 填入不合法回溯，重置状态
          board[y][x] = '.'
          ys[y][i] = false
          xs[x][i] = false
          cells[Math.floor(y / 3)][Math.floor(x / 3)][i] = false
        }
      }
    } else {
      // 填入数字，跳过
      return dfs(y, x + 1)
    }
    // 没有填入数字，但数字不合法,回溯
    return false
  }
  return dfs(0,0)
};
// @lc code=end

